/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
    let res = []
    restoreIpLevel(s, res, [], 0)
    return res
};

function restoreIpLevel(s, res, valArr, index) {
    if (valArr.length === 4) {
        if (index === s.length) {
            res.push(valArr.join("."))
        }
        return
    }

    let max = Math.min(index + 3, s.length)
    for (let i = index; i < max; i++) {
        let str = s.substr(index, i - index + 1),
            isValid = isValidIp(str);
        
        // 剪枝
        if (valArr.length === 3 && i !== s.length - 1) {
            continue
        }
        // 逻辑
        if (isValid) {
            valArr.push(str)
        } else {
            continue
        }
        restoreIpLevel(s, res, valArr, i + 1)
        if (isValid) {
            valArr.pop()
        }
    }
}

function isValidIp(s) {
    if (s === null || s === undefined || s === "") return false
    if (s.length > 3 || (s.length > 1 && s[0] === '0')) return false
    if (+s < 0 || +s > 255) return false
    return true
}